1. Field of the Invention
The present invention relates generally to digital data storage systems, such as disk drives, and in particular to prefetching data from a data storage system to a cache memory. Still more particularly, the present invention relates to a method and system for prefetching data where commands are reordered for execution.
2. Description of Related Art
A digital data storage system typically includes one or more storage devices that store data on storage media such as magnetic or optical data storage disks. Within magnetic disk drive systems, a head disk assembly generally consists of one or more hard disks and a hard disk drive controller that is utilized to manage local operations involving the hard disks. The hard disks are rigid platters, typically constructed of aluminum alloy or a mixture of glass and ceramic, which are covered with a magnetic coating. Generally, two or three platters are stacked vertically on a common spindle that is rotated by a disk drive motor.
The only other moving part within a typical hard drive assembly is a head positioning system that has a recording head associated with each side of each platter. In most modern drives, the recording heads are mounted at the end of small ceramic sliders that are elevated just above and below the platter""s surface. The sliders are supported by an air bearing surface that is self-pressurized by the airflows generated by the rapidly spinning disk. Each head is also connected to a flexible actuator arm that supports the entire head flying unit. More than one of such arms may be employed together to form a single armature unit.
Each head scans the hard disk platter surface during a xe2x80x9creadxe2x80x9d or xe2x80x9cwritexe2x80x9d operation. The head/arm assembly is positioned over the hard disk platter surface utilizing an actuator, also called a voice coil actuator, driven by a servo voice coil motor. The stator of the voice coil if motor is mounted to a base plate or casting on which is mounted a spindle supporting the disks. The base plate, in turn, is mounted to a frame via a compliant suspension. When current is applied to the motor, the voice coil motor develops a force, or torque, that is substantially proportional to the applied current. The arm acceleration is therefore substantially proportional to the magnitude of the applied current. As the head approaches the desired track, a reverse polarity signal, acting as a brake, is applied to the actuator, to cause the recording head to stop over a desired location on the platter surface.
After a disk drive controller receives an instruction from a user or a bus master, the controller causes a disk drive motor to actuate disk heads to move to the specified location and retrieve the requested data. The time required to store and retrieve data on disk drives is a function of four key parameters: seek times, rotational latencies, data transfer times and overheads. These factors are designed into the disk drive along with features incorporated into the drives to lessen the impact of these parameters in various workloads and logical environments. The term xe2x80x9cworkloadxe2x80x9d describes the dynamic qualities of the requests to store and retrieve data such as transfer length, transfer direction (to/from drive, store/retrieve or write/read), spatial location of data relative to past and future requests, and temporal location, i.e., how fast are the request/commands sent to the drive. xe2x80x9cLogical environmentxe2x80x9d describes the static qualities of the requests along with which features utilized in the drive are allowed to be employed. These features include data caching algorithms, command queuing and command reordering algorithms.
Seek time is the time required to position the disk head over the recording surface. Furthermore, because the disk drives have spinning media platters, a rotational latency while the platter spins to get the data in place for reading and writing is also introduced. Typically, disk I/O performance is dominated by these two factors, i.e., seek and latency, that are introduced by the mechanical parts of the disk in moving to a location where data is stored.
To minimize seek and rotational time delays, data storage systems incorporate disk data caches and command reordering algorithms that utilize command queuing. Disk caches take advantage of the principle of locality of references well known in the programming art. Typically the data from the disk is buffered into a memory device with a relatively fast access time. If the data requested already resides in the cache memory, the controller can transfer the data directly from the cache memory. Performance is increased because accessing data from the cache memory is substantially faster than accessing data from a disk drive.
Command reordering algorithms take advantage of a feature called command queuing. If commands are allowed to be queued, the host system can give the drive controller multiple requested commands, without the drive having completed prior requested commands. Besides other benefits, such as being able to overlap command overhead with seeking, latency and transferring data to/from disk, this means that the drive controller has multiple commands from which to choose a command to execute next. Algorithms can be employed that determine the xe2x80x9cbestxe2x80x9d candidate command to be executed next. The physical design of the disk drive e.g., seek times, latency, and how the data is laid out in the disk surface, along with host system design determine what is xe2x80x9cbest.xe2x80x9d For example, one algorithm may select the next command to be the one that would complete the soonest. Another algorithm may choose a combination of C commands such that the group of C commands would execute faster than any other groups of C commands. Another algorithm may take into account that executing certain types of commands, e.g., requests to certain blocks, reads versus writes, etc., would be better than other types of commands. Despite selecting the xe2x80x9cbestxe2x80x9d command to execute next, there is still xe2x80x9cextraxe2x80x9d time when the drive is not seeking or transferring data.
For workloads that frequently access data that is located near, and after, previously requested data, cache prefetch techniques are effective in increasing cache hit ratios. However, in high speed workload environments where queuing is employed and command reordering is allowed, any time not spent executing direct requests from a host system, i.e., prefetching data that may be subsequently requested, is considered xe2x80x9clostxe2x80x9d time.
There are currently three approaches to increase the cache hit ratio for the workload environments employing command reordering and queuing. One approach uses a minimum prefetch algorithm. As defined in the Small Computer Systems Interface (SCSI) standard, minimum prefetch instructs the drive that it must prefetch xe2x80x9cXxe2x80x9d amount of data blocks following the completion of read commands.
A second approach utilizes a cache segmentation scheme that forces the size of a given cache segment to hold the same amount of data as a physical track. Consequently, track caching algorithms then can require that an entire track be read before executing a subsequent command. Both these approaches involve forcing prefetching of data after the completion of previous commands. However, they also reduce the effectiveness of command reordering algorithms by not allowing certain xe2x80x9cbestxe2x80x9d command candidates to be executed.
The third approach prefetches data located prior to requested data on the next command to be executed, instead of prefetching data located after data requested from a previously executed command. This technique is commonly known as xe2x80x9cZero Latency Readsxe2x80x9d (ZLRs). An analysis of several workload environments, however, has indicated that data located after previously requested data is more likely to be accessed than data located before previously accessed data.
According, what is needed in the art is an improved and more efficient method for prefetching data that mitigates the above-discussed limitations.
It is therefore an object of the present invention to provide an improved data storage system.
It is another object of the present invention to provide an improved method and system for prefetching data.
To achieve the foregoing objects, and in accordance with the invention as embodied and broadly described herein, a method is disclosed for prefetching data for a cache memory from a mass-storage device having a controller that executes a plurality of commands. The method includes predetermining an extra time interval for each of the plurality of commands. Next, prior to executing a next command, data located subsequent to data requested from a committed, or presently executing, command is prefetched utilizing the predetermined extra time interval of the next command. In a related embodiment, the method includes executing a command reordering algorithm during which the seek and latency time periods of each of the plurality of commands is computed.
The present invention discloses a novel method for prefetching data that efficiently utilizes the xe2x80x9cextra timexe2x80x9d during which a disk drive is spinning accomplishing nothing. The present invention takes advantage of the condition that access time for subsequent commands in a non-sequential, i.e., reordered, workload environment is a function of both the rotational time between the end of the last block of data accessed for a previous command and the beginning of the first block of data for the next command executed, and the time it takes to seek the heads from one radial position to the target radial position on the disks. It should be noted that even though the seek time may be shorter than the rotational time, the total access time is equal to the rotational time. Furthermore, if the seek time is greater than the rotational time, the total access time is equal to the rotational time plus an integer number of complete revolution times.
The present invention prefetches data while minimizing the effects of seek times, rotational latencies and data rates in certain workload environments that have random-like spatial locality. Command queuing and reordering algorithms are employed in these workload environments to aid perceived disk drive speed, but inhibit traditional data caching methods from being very effective. In an advantageous embodiment, utilizing information, e.g., seek and latency periods, often gathered for typical command reordering algorithms, the present invention identifies extra time that the drive does not need to access subsequent commands selected by the reordering algorithm. It should be noted that in other advantageous embodiments, the present invention may be practiced with reordering algorithms that do not calculate seek and latency periods. In these situations, seek and latency times for the executable commands are computed separately. The identified extra time is effectively utilized in prefetching data.
The foregoing description has outlined, rather broadly, preferred and alternative features of the present invention so that those skilled in the art may better understand the detailed description of the invention that follows. Additional features of the invention will be described hereinafter that form the subject matter of the claims of the invention. Those skilled in the art should appreciate that they can readily use the disclosed conception and specific embodiment as a basis for designing or modifying other structures for carrying out the same purposes of the present invention. Those skilled in the art should also realize that such equivalent constructions do not depart from the spirit and scope of the invention in its broadest form.